Packet classification is employed by Internet routers to implement a number of advanced Internet services such as policy-based routing, rate-limiting, access control in firewalls, routing, service differentiation, traffic shaping, and traffic billing. Each of these services requires the router to classify incoming packets into different classes and then to perform appropriate actions depending upon the packet's specified class. For example, in packet routing applications, an incoming packet is classified to determine whether to forward or filter the packet, where to forward the packet to, what class of service the packet should receive, and/or how much should be charged for transmitting the packet. A packet classifier embodies a set of policies or rules that define what actions are to be taken based upon the contents of one or more fields of the packet's header. The packet header, which typically includes source and destination addresses, source and destination port numbers, protocol information, and so on, can match more than one rule. For example, one rule in a firewall application can specify either a “permit” or “deny” action for a given set of source and destination addresses, another rule in the firewall application can specify either a “permit” or “deny” action for a given protocol, and yet another rule in the firewall application can specify either a “permit” or “deny” action for a particular source address and protocol.
More specifically, in firewall applications, packet classification is performed using a collection of rules commonly known as an access control list (ACL), which is typically generated by a system administrator using well-known tools and then programmed in the routers using well-known firmware. For example, system administrators create control lists based on sets of machines and flows, and then use ACL tools to flatten the control lists into individual access control lines or rules, which are then stored in an ACL table.
Many network processors employ ternary content addressable memory (TCAM) devices to store the rules of various ACLs. During packet classification operations, selected information from an incoming packet's header can be simultaneously compared with all the rules stored in the TCAM device, thereby allowing packet classification to be performed at very high speeds. However, although capable of very fast searching speeds, TCAM devices are relatively large and expensive, as compared to RAM-based hash systems (e.g., because each TCAM cell includes two RAM cells and a compare circuit). As the amount of network traffic continually increases, the size and complexity of the ACL rules required to be stored in packet classification devices increases, which in turn makes TCAM-based packet classification solutions increasingly expensive to deploy in advanced Internet services such as firewall applications.
Thus, there is a need to reduce the amount of memory area in the TCAM portion of a packet classification device required to store ACLs for advanced Internet services such as firewall systems, intrusion detection systems, and other applications.
Like reference numerals refer to corresponding parts throughout the drawing figures.